//
// Created by LaiChao on 2021/6/17.
//
// 关于图的四种不同路径规划算法：广度优先遍历、Early Exit、迪杰斯特拉算法和A*算法

#ifndef THEROADTOADVANCEMENT_GRAPHROUTING_H
#define THEROADTOADVANCEMENT_GRAPHROUTING_H

#include <unordered_map>
#include <vector>
#include <array>
#include <unordered_set>
#include <algorithm>

using namespace std;

////////////////////////////////////////////////////////////////////////////////////////
//                                  Graph Definition                                  //
////////////////////////////////////////////////////////////////////////////////////////
struct SimpleGraph {
    unordered_map<char, vector<char>> edges;

    vector<char> neighbors(char id) {
        return edges[id];
    }
};

// Test Graph
SimpleGraph example_graph{{
                                  {'A', {'B'}},
                                  {'B', {'C'}},
                                  {'C', {'B', 'D', 'F'}},
                                  {'D', {'C', 'E'}},
                                  {'E', {'F'}},
                                  {'F', {}},
                          }};
struct GridLocation {
    int x, y;
};

namespace std {
/* implement hash function so we can put GridLocation into an unordered_set */
    template<>
    struct hash<GridLocation> {
        typedef GridLocation argument_type;
        typedef std::size_t result_type;

        std::size_t operator()(const GridLocation &id) const noexcept {
            return std::hash<int>()(id.x ^ (id.y << 4));
        }
    };
}

struct SquareGrid {
    int width, height;
    static std::array<GridLocation, 4> DIRS;    // For direction: -1, 1, 0, 0
    std::unordered_set<GridLocation> walls;

    SquareGrid(int width_, int height_) : width(width_), height(height_) {}

    bool in_bounds(GridLocation id) const {
        return id.x >= 0 && id.x < width && id.y >= 0 && id.y < height;
    }

    bool passable(GridLocation id) const {
        return walls.find(id) == walls.end();   // 当前位置不能是墙
    }

    // 找到当前点的所有周围点，输出坐标
    vector<GridLocation> neighbors(GridLocation id) const {
        vector<GridLocation> results;
        for (GridLocation &dir:DIRS) {
            GridLocation next{id.x + dir.x, id.y + dir.y};
            if (in_bounds(next) && passable(next)) results.push_back(next);
        }
        // see "Ugly paths" section for an explanation: .....Why???
        if ((id.x + id.y) % 2 == 0) reverse(results.begin(), results.end());
        return results;
    }
};

// Assignment
array<GridLocation, 4>SquareGrid::DIRS = {
        GridLocation{1, 0},
        GridLocation{-1, 0},
        GridLocation{0, 1},
        GridLocation{0, -1},
};

bool operator==(const GridLocation &a, const GridLocation &b) {
    return a.x == b.x && a.y == b.y;
}

bool operator!=(const GridLocation &a, const GridLocation &b) {
    return !(a == b);
}


#endif //THEROADTOADVANCEMENT_GRAPHROUTING_H
